package first

import "math"

/*
	我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
	示例:

	输入: n = 10
	输出: 12
	解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
	说明:

	1是丑数。
	n不超过1690。

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/chou-shu-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/*
	每一个丑数都只能是小于它的丑数与质因子的乘积
*/
func nthUglyNumber(n int) int {
	if n == 1 {
		return 1
	}
	a, b, c := 2, 3, 5 // 质因子
	dp := make([]int, n+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = math.MaxInt32
	}
	dp[1] = 1
	dp[0] = 0
	// dp[i] = min(factor*dp[j])

	for i := 2; i <= n; i++ {
		for j := 1; j < i; j++ {
			if dp[j]*a > dp[i-1] {
				dp[i] = min(dp[i], a*dp[j])
			}
			if dp[j]*b > dp[i-1] {
				dp[i] = min(dp[i], b*dp[j])
			}
			if dp[j]*c > dp[i-1] {
				dp[i] = min(dp[i], c*dp[j])
			}
		}
	}

	return dp[n]
}

/*
func nthUglyNumber(n int) int {
	a, b, c := 0, 0, 0
	dp := make([]int, n)
	dp[0] = 1
	for i := 1; i < n; i++ {
		f2, f3, f5 := dp[a]*2, dp[b]*3, dp[c]*5
		dp[i] = min(f2, min(f3, f5))
		if dp[i] == f2 {
			a++
		}
		if dp[i] == f3 {
			b++
		}
		if dp[i] == f5 {
			c++
		}
	}
	return dp[n-1]
}
*/

/*
	a, b, c | f2, f3, f5
1	1, 0, 0 | 2, 3, 5 --> 2
2	1, 1, 0 | 4, 3, 5 --> 3
3	2, 1, 1 | 4, 6, 5 --> 4
4	2, 1, 2 | 6, 6, 5 --> 5
5	3, 2, 2 | 6, 6, 15 --> 6
6	4, 2, 2 | 8, 9, 15 --> 8
7	4, 3, 2 | 10, 9, 15 --> 9
8	5, 3, 2 | 10, 12, 15 --> 10
9	6, 4, 2 | 12, 12, 15 --> 12
10	6, 5, 4 | 16, 15, 15 --> 15
11	7, 5, 4 | 16, 18, 20 --> 16
*/
